package org.common.util;

public class StringUtil {

	public static void main(String args[]) {
		System.out.println(maxSubstring("asdfdsaf","adfgfdsfgfg"));
	}

	// 求解两个字符号的最长公共子串
	public static String maxSubstring(String strOne, String strTwo) {
		// 参数检查
		if (strOne == null || strTwo == null) {
			return null;
		}
		if (strOne.equals("") || strTwo.equals("")) {
			return null;
		}
		// 矩阵的横向长度
		int len1 = strOne.length();
		// 矩阵的纵向长度
		int len2 = strTwo.length();

		// 保存矩阵的上一行
		int[] topLine = new int[len1];
		// 保存矩阵的当前行
		int[] currentLine = new int[len1];
		// 矩阵元素中的最大值
		int maxLen = 0;
		// 矩阵元素最大值出现在第几列
		int pos = 0;
		char ch = ' ';
		for (int i = 0; i < len2; i++) {
			ch = strTwo.charAt(i);
			// 遍历str1，填充当前行的数组
			for (int j = 0; j < len1; j++) {
				if (ch == strOne.charAt(j)) {
					// 如果当前处理的是矩阵的第一列，单独处理，因为其坐上角的元素不存在
					if (j == 0) {
						currentLine[j] = 1;
					} else {
						currentLine[j] = topLine[j - 1] + 1;
					}
					if (currentLine[j] > maxLen) {
						maxLen = currentLine[j];
						pos = j;
					}
				}
			}
			// 将矩阵的当前行元素赋值给topLine数组; 并清空currentLine数组
			for (int k = 0; k < len1; k++) {
				topLine[k] = currentLine[k];
				currentLine[k] = 0;
			}
			// 或者采用下面的方法
			// topLine = currentLine;
			// currentLine = new int[len1];
		}
		return strOne.substring(pos - maxLen + 1, pos + 1);
	}

	static void getLCS(String str1, String str2) {
		int len1 = str1.length();
		int len2 = str2.length();
		int[] matrix = new int[len1];
		for (int i = 0; i < len1; i++) {
			matrix[i] = 0;
		}
		int[] maxValue = new int[len2];
		int[] maxIndex = new int[len2];
		for (int i = 0; i < len2; i++) {
			maxValue[i] = -1;
			maxIndex[i] = -1;
		}
		for (int i = 0; i < len2; i++) {
			for (int j = len1 - 1; j >= 0; j--) {
				if (str2.charAt(i) == str1.charAt(j)) {
					if (j == 0) {
						matrix[j] = 1;
					} else {
						matrix[j] = matrix[j - 1] + 1;
					}
				} else {
					matrix[j] = 0;
				}
				if (matrix[j] != 0 && matrix[j] > maxValue[0]) {
					maxValue[0] = matrix[j];
					maxIndex[0] = j;
					for (int i1 = 1; i1 < len2; i1++) {
						maxValue[i1] = -1;
						maxIndex[i1] = -1;
					}
				} else if (matrix[j] == maxValue[0]) {
					for (int i1 = 1; i1 < len2; i1++) {
						if (maxValue[i1] == -1) {
							maxValue[i1] = matrix[j];
							maxIndex[i1] = j;
							break;
						}
					}
				}
			}
		}
		for (int i = 0; i < len2; i++) {
			if (maxValue[i] > 0) {
				System.out.println("第" + (i + 1) + "个公共子串");
				for (int j = maxIndex[i] - maxValue[i] + 1; j <= maxIndex[i]; j++) {
					System.out.print(str1.charAt(j));
				}
				System.out.println();
			}
		}
	}

}
